#include <thread>
#include <mutex>
#include <iostream>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>
#include <cassert>


//-----------------------------------------------------------------------------

using uint = unsigned int;
using uint_vector = std::vector<uint>;

//-----------------------------------------------------------------------------

void print(const uint_vector& uints, const std::string& title) {
    std::cout << title << ": ";
    for (auto x : uints) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

//-----------------------------------------------------------------------------

uint_vector generate_random_uints(const size_t num_uints) {
    std::random_device rand_dev;

    // mersenne twister pseudo-random number generator (engine)
    // use std::random_device to generate random seed
    std::mt19937 mt_engine(rand_dev());

    std::uniform_int_distribution<uint> gen_uint(1, 10);

    uint_vector generated;

    for (size_t i = 0; i < num_uints; ++i) {
        generated.push_back(
            gen_uint(mt_engine)
        );
    }

    return generated;
};

//-----------------------------------------------------------------------------

uint_vector sleep_sort(const uint_vector& uints) {
    std::mutex mtx;
    uint_vector sorted;

    std::vector<std::thread> threads;

    for (auto x : uints) {
        threads.emplace_back(
            [x, &mtx, &sorted]() {
                std::this_thread::sleep_for( std::chrono::seconds(x) );
                std::lock_guard<std::mutex> lock(mtx);
                sorted.push_back(x);
            }
        );
    }

    for (auto& t : threads) {
        t.join();
    }

    assert( std::is_sorted(sorted.begin(), sorted.end()) );

    return sorted;
}

//-----------------------------------------------------------------------------

const size_t NUMS_TO_SORT = 25;

int main() {
    const auto random_uints = std::move(generate_random_uints(NUMS_TO_SORT));
    print(random_uints, "input");

    const auto sorted_uints = std::move(sleep_sort(random_uints));
    print(sorted_uints, "sorted");

    return 0;
}
